Introduction to Computer Science [CS50x] [Harvard] [2018]

o

amazon.com

o

amazon.com

o

<xo o

llll

VIrll

»»»•

llll

HG85

.. .

* *

A 4

0 0 0

0 TUI

0 0 0

0 0 0

tumblr.com

linear search

for each element in array

if element you’re looking for
return true

return false

binary search

look at middle of sorted array
if element you're looking for
return true

else if element is to left

search left half of array
else if element is to right

search right half of array

else

return false

Exa?nination Book

Name _

Subject _

Instructor _

Class _

Book No _

Section
Date _

PONTIAC PAPER CO.
"Home of the Blue Books"

777 Header *00 BWd.. Folcrofl, PA 19032 0183
(•10) M3-B500 FAX (610) M3 4927

bubble sort

repeat until no swaps

for i from 0 to n-2

if i’th and i+l’th
swap them

elements out of order

selection sort

for i from 0 to n-1

find smallest element between i 1 th and n-l'th
swap smallest with i 1 th element

insertion sort

for i from 1 to n-1

call 0’th through i-l f th elements the
remove i*th element

insert it into sorted side in order

"sorted side"

algorithms

running time

time to solve

size of problem

time to solve

n

size of problem

bubble sort

(n-1)

(n- 1) + (n-2)

(n- 1) + (n-2) + ... + 1

(n- 1) + (n

n(n

2 ) + ... + 1
1)/2

(n- 1) + (n-2) + ... + 1

n(n- 1)/2
( n 2 - ri)/2

(n- 1) + (n-2) + ... + 1

n(n- 1)/2
( n 2 - ri)/2
n 2 l 2 - n/2

1 , 000,000

n 2 /2 - nl 2

n 2 / 2

1 , 000 , 000 2 /2

n/2

1 , 000 , 000/2

n 2 /2 - n/2

1 , 000 , 0002 / 2 - 1 , 000 , 000/2

500,000,000,000 - 500,000

n 2 /2 - n/2

1 , 000 , 0002 / 2 - 1 , 000 , 000/2

500 , 000 , 000,000 - 500,000

499 , 999 , 500,000

n 2 /2 - n/2

CXn 2 )

o

0(n 2 )

0(n log n)
O(n)

0(log n)

0 ( 1 )

0(n 2 )

0(n log n )
O(n)

0(log n)

0 ( 1 )

0(n 2 )

0(n log n)
O(n)

0(log n)

0 ( 1 )

Cl

Q(n 2 )

0(n log n)

Q(n)

Q(log n)

0 ( 1 )

0(n 2 )

Q{n log n )

0(n)

©(log n)

0 ( 1 )

merge sort

On input of n elements
if n < 2
return

else

sort left half of elements
sort right half of elements
merge sorted halves

42756831

42756831

2

2 4

2 4

2 4

2 4

2 4

2 4

2

4

5

6 8

3 1

J

2

7

6 8

3 1

J

6 8

3 1

J

L

L

L

l-

2

6 8

3 1

J

5 7

2 4

L

L

L

l-

7

2 4 5

6 8

3 1

J

L

L

L

l-

2 4 5 7

6 8

3 1

J

L

L

2 4 5 7

6 8 3 1

2 4 5 7

2 4 5 7

L

L

L

l-

2 4 5 7

6

2 4 5 7

2 4 5 7

2 4 5 7

2 4 5 7

6 8

1 3

2 4 5 7

6 8

3

2 4 5 7

1

6 8

2 4 5 7

1 3

00

2 4 5 7

13 6

1

1 2

12 3

12 3 4

12345678

12345678

0(n log n)

on input of n elements
if n < 2
return

else

sort left half of elements
sort right half of elements
merge sorted halves

on input of n elements
if n < 2
return

else

sort left half of elements
sort right half of elements
merge sorted halves

T(n) = 0(1)

if n < 2

T(n) = 0(1)

if n < 2

on input of n elements
if n < 2
return

else

sort left half of elements
sort right half of elements
merge sorted halves

on input of n elements
if n < 2
return

else

sort left half of elements
sort right half of elements
merge sorted halves

on input of n elements
if n < 2
return

else

sort left half of elements
sort right half of elements
merge sorted halves

T(n) = T(n/ 2) + T(n/2) + 0(n)

if n > 2

71 n) = 77 n/2) + 7Tn/2) + 0(n)

if n > 2

71 n) = 77 n/2) + 7Tn/2) + 0(n)

if n > 2

71 n) = 77 n/2) + 7Tn/2) + 0(n)

if n > 2

0(n log n)

0(n log n)

on input of n elements
if n < 2
return

else

sort left half of elements
sort right half of elements
merge sorted halves

hap py birth day to you

£

hap py birth day

1

* W

—9 - 0 --- 9 -

hap py birth day to you

—9 - 9 -

hap py birth day

dear

some

one

to you